package UnitTest;

import java.util.ArrayList;
import java.util.List;

/**
 * @Auther: Administrator
 * @Date: 2019/9/10/010 19 58
 * @Description:
 */
public class ReverseLinkedList {

    public static void main(String[] args) {
        Node2 node5 = new Node2(5);
        Node2 node3 = new Node2(3, node5);
        Node2 node4 = new Node2(4, node3);
        Node2 node1 = new Node2(1, node4);
        Node2 node2 = new Node2(2, node1);
        System.out.println(reverseLinkedList(node2,2));
    }

    /**
     * 反转链表
     * @param m  反转参数
     * @param head 链表头
     */
    public static Node2 reverseLinkedList(Node2 head,int m) {
        if (head == null || m == 0) {
            return null;
        } else if (head.next == null) {
            return head;
        }
        List<Node2> nodeList = new ArrayList<>(m);
        Node2 temp = head;
        for (int i = 0; i < m; i++) {
            nodeList.add(temp);
            if (temp.next != null) {
                temp = temp.next;
            }
        }
        //list反转
        reverse(nodeList, 0, nodeList.size() - 1);
        //用反转的list拼接
        for (int j = 0; j < nodeList.size(); j++) {
            Node2 node = nodeList.get(j);
            if (j + 1 < nodeList.size()) {
                node.next = nodeList.get(j + 1);
            }
        }
        // 每一个反转的list的node尾部的next ，要等下一个递归的head返回了才能确定
        if (temp != null) {
            Node2 lastNode = nodeList.get(nodeList.size()-1);
            lastNode.next = reverseLinkedList(temp, m);
        }
        return nodeList.get(0);
    }

    /**
     * list反转start和end
     * @param list 列表
     * @param start 开始
     * @param end 结束
     */
    public static List reverse(List list,int start,int end) {
        if (list == null || list.size() <= 1||start==end||start>end)
            return list;
        Object o1 = list.get(start);
        Object o2 = list.get(end);
        //替换list两个位置的值
        list.set(end,o1);
        list.set(start,o2);
        return reverse(list,start+1,end-1);
    }

    //辅助类
    static class Node2 {
        int value;
        Node2 next;

        public Node2(int value, Node2 node) {
            this.value = value;
            this.next = node;
        }

        public Node2(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node2{" +
                    "value=" + value +
                    '}';
        }
    }



}
